package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class Demo4 {
    //LCR 024. 反转链表
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    //24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode newHead = head.next;
        head.next = swapPairs(head.next.next);
        newHead.next = head;

        return newHead;
    }

    //2331. 计算布尔二叉树的值
    public boolean evaluateTree(TreeNode root) {
        if(root.left == null) return root.val == 1;

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val==2?left || right:left && right;
    }


    //LCR 049. 求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        if(root.left == null && root.right == null) return root.val;
        return sum(root, 0);
    }
    private int sum(TreeNode root, int presum) {
        presum = presum * 10 + root.val;
        if(root.left == null && root.right == null) return presum;
        int left = 0, right = 0;
        if(root.left != null)  left = sum(root.left, presum);
        if(root.right != null) right = sum(root.right, presum);
        return left + right;
    }


    //LCR 047. 二叉树剪枝
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) return null;

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left == null && root.right == null && root.val == 0) return null;
        return root;
    }


    //98. 验证二叉搜索树
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        boolean left = isValidBST(root.left);
        if(!left) return false;
        if(root.val <= prev) return false;

        prev = root.val;
        return isValidBST(root.right);
    }


    //230. 二叉搜索树中第K小的元素
    int count;
    int ret = -1;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inorder(root);
        return ret;
    }
    private void inorder(TreeNode root) {
        if(root == null) return;

        if(count > 0) inorder(root.left);
        if(--count == 0)
            ret = root.val;
        if(count > 0) inorder(root.right);
    }


    //257. 二叉树的所有路径
    List<String> ret1;
    public List<String> binaryTreePaths(TreeNode root) {
        ret1 = new ArrayList<>();
        dfs(root, new StringBuilder());
        return ret1;
    }
    private void dfs(TreeNode root, StringBuilder _path) {
        StringBuilder path = new StringBuilder(_path);
        path.append(Integer.toString(root.val));
        if(root.left == null && root.right == null) {
            ret1.add(path.toString());
            return;
        }

        path.append("->");
        if(root.left != null) dfs(root.left, path);
        if(root.right != null) dfs(root.right, path);
    }


    //46. 全排列
    List<List<Integer>> ret2;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {
        ret2 = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];

        dfs(nums);
        return ret2;
    }
    private void dfs(int[] nums) {
        if(nums.length == path.size()) {
            ret2.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!check[i]) {
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                // 回溯 -> 恢复现场
                path.remove(path.size() - 1);
                check[i] = false;
            }
        }
    }



    //LCR 079. 子集
    List<List<Integer>> ret3;
    List<Integer> path3;
    public List<List<Integer>> subsets(int[] nums) {
        ret3 = new ArrayList<>();
        path3 = new ArrayList<>();

        dfs(nums, 0);
        return ret3;
    }
    private void dfs(int[] nums, int k) {
        ret3.add(new ArrayList<>(path));

        for(int i = k; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }



    //1863. 找出所有子集的异或总和再求和
    int path4;
    int ret4;
    public int subsetXORSum(int[] nums) {
        dfs4(nums, 0);
        return ret;
    }

    private void dfs4(int[] nums, int pos) {
        for(int i = pos; i < nums.length; i++) {
            path4 ^= nums[i];
            dfs(nums, i + 1);
            ret4 += path4;
            path4 ^= nums[i];   // 恢复现场
        }
    }



    //LCR 084. 全排列 II 
    List<List<Integer>> ret5;
    List<Integer> path5;
    boolean[] check5;

    public List<List<Integer>> permuteUnique(int[] nums) {
        ret5 = new ArrayList<>();
        path5 = new ArrayList<>();
        check5 = new boolean[nums.length];

        Arrays.sort(nums);
        dfs5(nums);
        return ret5;
    }
    private void dfs5(int[] nums) {
        if(path.size() == nums.length) {
            ret5.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!check[i] && (i == 0 ||  nums[i] != nums[i - 1] || check[i - 1] == true)) {
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                path.remove(path.size() - 1);
                check[i] = false;
            }
        }
    }



    //784. 字母大小写全排列
    List<String> ret6;
    StringBuffer path6;

    public List<String> letterCasePermutation(String s) {
        ret6 = new ArrayList<>();
        path6 = new StringBuffer();

        dfs(s, 0);
        return ret6;
    }

    private void dfs(String s, int pos) {
        if(pos == s.length()) {
            ret6.add(path.toString());
            return;
        }

        // 不转变
        char ch = s.charAt(pos);
        path6.append(ch);
        dfs(s, pos + 1);
        path6.deleteCharAt(path6.length() - 1);

        // 大小写转变
        if(ch < '0' || ch > '9') {
            if(ch >= 'a' && ch <= 'z') ch -= 32;
            else ch += 32;
            path6.append(ch);
            dfs(s, pos + 1);
            path6.deleteCharAt(path6.length() - 1);
        }
    }


    // 17. 电话号码的字母组合
    //List<String> ret;
    //    StringBuffer path;
    //    String[] flag =  new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    //
    //    public List<String> letterCombinations(String digits) {
    //        ret = new ArrayList<>();
    //        if(digits.length() == 0) return ret;
    //        path = new StringBuffer();
    //
    //        dfs(digits.toCharArray(), 0);
    //        return ret;
    //    }
    //
    //    private void dfs(char[] arr, int pos) {
    //        if(path.length() == arr.length) {
    //            ret.add(new String(path));
    //            return;
    //        }
    //
    //        for(int i = 0; i < flag[arr[pos]-'0'].length(); i++) {
    //            path.append(flag[arr[pos]-'0'].charAt(i));
    //            dfs(arr, pos + 1);
    //            path.deleteCharAt(path.length() - 1);
    //        }
    //    }


    // 22. 括号生成
    //List<String> ret;
    //    StringBuffer path;
    //
    //    public List<String> generateParenthesis(int n) {
    //        ret = new ArrayList<>();
    //        path = new StringBuffer();
    //
    //        dfs(n, 0, 0);
    //        return ret;
    //    }
    //    private void dfs(int n, int left, int right) {
    //        if(path.length() == n * 2) {
    //            ret.add(path.toString());
    //            return;
    //        }
    //
    //        if(left < n) {
    //            path.append('(');
    //            dfs(n, left + 1, right);
    //            path.deleteCharAt(path.length() - 1);
    //        }
    //
    //        if(left > right) {
    //            path.append(')');
    //            dfs(n, left, right + 1);
    //            path.deleteCharAt(path.length() - 1);
    //        }
    //    }



    //LCR 080. 组合
    // List<List<Integer>> ret;
    //    List<Integer> path;
    //    int n, k;
    //
    //    public List<List<Integer>> combine(int _n, int _k) {
    //        ret = new ArrayList<>();
    //        path = new ArrayList<>();
    //        n = _n; k = _k;
    //
    //        dfs(1);
    //        return ret;
    //    }
    //
//        private void dfs(int pos) {
//            if(path.size() == k) {
//                ret.add(new ArrayList<>(path));
//                return;
//            }
//
//            for(int i = pos; i <= n; i++) {
//                path.add(i);
//                dfs(i + 1);
//                path.remove(path.size() - 1);
//            }
//        }



    //494. 目标和
    //    int ret;
    //    int target;
    //
    //    public int findTargetSumWays(int[] nums, int _target) {
    //        target = _target;
    //        dfs(nums, 0, 0);
    //        return ret;
    //    }
    //
    //    private void dfs(int[] nums, int pos, int path) {
    //        if(pos == nums.length) {
    //            if(path == target) ret++;
    //            return;
    //        }
    //
    //        dfs(nums, pos + 1, path + nums[pos]);
    //        dfs(nums, pos + 1, path - nums[pos]);
    //    }



    // LCR 081. 组合总和
    //    List<List<Integer>> ret;
    //    List<Integer> path;
    //    int target;
    //
    //    public List<List<Integer>> combinationSum(int[] nums, int _target) {
    //        ret = new ArrayList<>();
    //        path = new ArrayList<>();
    //        target = _target;
    //
    //        dfs(nums, 0, 0);
    //        return ret;
    //    }
    //
    //    private void dfs(int[] nums, int pos, int sum) {
    //        if(sum == target) {
    //            ret.add(new ArrayList<>(path));
    //            return;
    //        }
    //
    //        int i = 0;
    //        for(; pos < nums.length && sum < target; i++) {
    //            if(i != 0) {
    //                path.add(nums[pos]);
    //                sum += nums[pos];
    //            }
    //            dfs(nums, pos + 1, sum);
    //        }
    //        while(i-- > 1) path.remove(path.size() - 1);
    //    }



    // 526. 优美的排列
    //int ret;
    //    int path;
    //    boolean[] check;
    //
    //    public int countArrangement(int n) {
    //        check = new boolean[n + 1];
    //        dfs(n, 1);
    //        return ret;
    //    }
    //
    //    private void dfs(int n, int pos) {
    //        if(path == n) {
    //            ret++;
    //            return;
    //        }
    //
    //        for(int i = 1; i <= n; i++) {
    //            if(!check[i] && (i % pos == 0 || pos % i == 0)) {
    //                check[i] = true; path++;
    //                dfs(n, pos + 1);
    //                check[i] = false; path--;       //恢复现场
    //            }
    //        }
    //    }



    // 51. N 皇后
    //    List<List<String>> ret;
    //    List<String> path;
    //    StringBuffer _tmp;
    //    boolean[] col;      // 记录该列是否有皇后
    //    boolean[] a;        // 记录正对角线是否有皇后
    //    boolean[] b;        // 记录反对角线是否有皇后
    //
    //    public List<List<String>> solveNQueens(int n) {
    //        ret = new ArrayList<>();
    //        col = new boolean[n];
    //        path = new ArrayList<>();
    //        a = new boolean[n * 2];
    //        b = new boolean[n * 2];
    //        _tmp = new StringBuffer();
    //        for(int i = 0; i < n; i++) _tmp.append('.');
    //
    //        dfs(n, 0);
    //        return ret;
    //    }
    //
    //    private void dfs(int n, int pos) {  //pos 记录当前行数
    //        if(path.size() == n) {
    //            ret.add(new ArrayList<>(path));
    //            return;
    //        }
    //
    //        // i 表示当前所处的列
    //        for(int i = 0; i < n; i++) {
    //            if(col[i] == false && !a[i - pos + n] && !b[i + pos]) {
    //                StringBuffer tmp = new StringBuffer(_tmp);
    //                tmp.setCharAt(i, 'Q');
    //                path.add(tmp.toString());
    //                col[i] = true; a[i - pos + n] = true; b[i + pos] = true;
    //                dfs(n, pos + 1);
    //                path.remove(path.size() - 1);      // 恢复现场
    //                col[i] = false; a[i - pos + n] = false; b[i + pos] = false;
    //            }
    //        }
    //    }



    //36. 有效的数独
    // public boolean isValidSudoku(char[][] board) {
    //        boolean[][] col = new boolean[9][10];
    //        boolean[][] row = new boolean[9][10];
    //        boolean[][][] cube = new boolean[3][3][10];
    //
    //        for(int i = 0; i < 9; i++) {
    //            for(int j = 0; j < 9; j++) {
    //                if(board[i][j] == '.') continue;
    //                char ch = board[i][j];
    //                if(row[i][ch - '0'] || col[j][ch - '0'] || cube[i/3][j/3][ch - '0']) {
    //                    return false;
    //                } else {
    //                    row[i][ch - '0'] = col[j][ch - '0'] = cube[i/3][j/3][ch - '0'] = true;
    //                }
    //            }
    //        }
    //
    //        return true;
    //    }


    //37. 解数独

    //boolean[][] col;
    //    boolean[][] row;
    //    boolean[][][] cube;
    //    int count;
    //
    //    public void solveSudoku(char[][] board) {
    //        col = new boolean[9][10];
    //        row = new boolean[9][10];
    //        cube = new boolean[3][3][10];
    //
    //        // 初始化
    //        for(int i = 0; i < 9; i++) {
    //            for(int j = 0; j < 9; j++) {
    //                int num = board[i][j] - '0';
    //                if(board[i][j] != '.')
    //                    row[i][num] = col[j][num] = cube[i / 3][j / 3][num] = true;
    //            }
    //        }
    //
    //        dfs(board);
    //    }
    //    private boolean dfs(char[][] board) {
    //
    //        for(int i = 0; i < 9; i++) {
    //            for(int j = 0; j < 9; j++) {
    //                if(board[i][j] != '.') continue;
    //
    //                int k = 1;
    //                for(; k <= 9; k++) {
    //                    // 剪枝
    //                    if(!row[i][k] && !col[j][k] && !cube[i/3][j/3][k]) {
    //                        board[i][j] = (char) (k + '0');
    //                        row[i][k] = col[j][k] = cube[i/3][j/3][k] = true;
    //                        boolean flag = dfs(board);
    //                        if(flag) return true;
    //
    //                        // 恢复现场
    //                        row[i][k] = col[j][k] = cube[i/3][j/3][k] = false;
    //                        board[i][j] = '.';
    //                    }
    //                }
    //                if(k > 9) return false;
    //            }
    //        }
    //        return true;
    //    }



    // 79. 单词搜索
    //boolean[][] visit;
    //    public boolean exist(char[][] board, String word) {
    //        int row = board.length;
    //        int col = board[0].length;
    //        visit = new boolean[row][col];
    //
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(board[i][j] == word.charAt(0)) {
    //                    visit[i][j] = true;
    //                    if(dfs(board, i, j, word, 1)) return true;
    //                    visit[i][j] = false;
    //                }
    //            }
    //        }
    //        return false;
    //    }
    //
    //    int[] dx = new int[]{0, 0, 1, -1};
    //    int[] dy = new int[]{1, -1, 0, 0};
    //    private boolean dfs(char[][] board, int i, int j, String word, int pos) {
    //        if(pos == word.length()) return true;
    //
    //        // 从i, j 位置的四周开始寻找字符串中 pos下标的字母
    //        int row = board.length;
    //        int col = board[0].length;
    //
    //        for(int n = 0; n < 4; n++) {
    //            i += dx[n]; j += dy[n];
    //            if(i >= 0 && i < row && j >= 0 && j < col && !visit[i][j] && board[i][j] == word.charAt(pos)) {
    //                visit[i][j] = true;
    //                if(dfs(board, i, j, word, pos + 1)) return true;
    //                visit[i][j] = false;    // 恢复现场
    //            }
    //            i -= dx[n]; j -= dy[n];
    //        }
    //
    //        return false;
    //    }




    //1219. 黄金矿工
    //boolean[][] visit;
    //    int ret;
    //    int row;
    //    int col;
    //
    //    public int getMaximumGold(int[][] grid) {
    //        row = grid.length;
    //        col = grid[0].length;
    //        visit = new boolean[row][col];
    //
    //        // 从每个黄金数目不为0的单元依次进行尝试
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(grid[i][j] != 0) {
    //                    visit[i][j] = true;
    //                    dfs(grid, i, j, grid[i][j]);
    //                    visit[i][j] = false;
    //                }
    //            }
    //        }
    //
    //        return ret;
    //    }
    //
    //    int[] dx = new int[]{0, 0, 1, -1};
    //    int[] dy = new int[]{1, -1, 0, 0};
    //
    //    private void dfs(int[][] grid, int x, int y, int sum) {
    //        for(int k = 0; k < 4; k++) {
    //            int i = x + dx[k], j = y + dy[k];
    //            if(i >= 0 && i < row && j >= 0 && j < col && !visit[i][j] && grid[i][j] != 0) {
    //                visit[x][y] = true;
    //                dfs(grid, i, j, sum + grid[i][j]);
    //                visit[i][j] = false;
    //            } else {
    //                ret = Math.max(ret, sum);
    //            }
    //        }
    //    }



    // 980. 不同路径 III
    //int ret;
    //    int step;   // 记录 空方格的个数
    //    int row;
    //    int col;
    //    boolean[][] visit;
    //
    //    int[] dx = new int[]{0, 0, 1, -1};
    //    int[] dy = new int[]{1, -1, 0, 0};
    //
    //    public int uniquePathsIII(int[][] grid) {
    //        row = grid.length;
    //        col = grid[0].length;
    //        visit = new boolean[row][col];      // 标记空方格是否走过
    //
    //        int m = 0, n = 0;       // 记录 起始方格的下标
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(grid[i][j] == 1) {
    //                    m = i; n = j;
    //                } else if(grid[i][j] == 0) {
    //                    step++;
    //                }
    //            }
    //        }
    //
    //        dfs(grid, m, n, 0);
    //        return ret;
    //    }
    //
    //    private void dfs(int[][] grid, int m, int n, int count) {
    //
    //         for(int k = 0; k < 4; k++) {
    //            int x = m + dx[k], y = n + dy[k];
    //            if(x >= 0 && x < row && y >= 0 && y < col && !visit[x][y] && grid[x][y] == 0) {
    //                visit[x][y] = true;
    //                dfs(grid, x, y, count + 1);
    //                visit[x][y] = false;
    //            }
    //            if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 2 && count == step) {
    //                ret++;
    //            }
    //        }
    //    }



    //733. 图像渲染
    //int row;
    //    int col;
    //
    //    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    //        row = image.length;
    //        col = image[0].length;
    //
    //        dfs(image, sr, sc, image[sr][sc], color);
    //        return image;
    //    }
    //
    //    int[] dx = new int[]{0, 0, 1, -1};
    //    int[] dy = new int[]{1, -1, 0, 0};
    //    private void dfs(int[][] image, int i, int j, int oldColor, int newColor) {
    //        image[i][j] = newColor;
    //
    //        for(int k = 0; k < 4; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            // 当前值与要修改的值相同，则不进行递归，防止死循环造成栈溢出
    //            if(x >= 0 && x < row && y >= 0 && y < col && image[x][y] == newColor) continue;
    //            if(x >= 0 && x < row && y >= 0 && y < col && image[x][y] == oldColor) {
    //                dfs(image, x, y, oldColor, newColor);
    //            }
    //        }
    //    }



    //200. 岛屿数量
    //int row, col;
    //
    //    public int numIslands(char[][] grid) {
    //        row = grid.length;
    //        col = grid[0].length;
    //
    //        int ret = 0;
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(grid[i][j] == '1') {
    //                    dfs(grid, i, j);
    //                    ret++;
    //                }
    //            }
    //        }
    //        return ret;
    //    }
    //
    //    int[] dx = new int[]{0, 0, 1, -1};
    //    int[] dy = new int[]{1, -1, 0, 0};
    //    private void dfs(char[][] grid, int i, int j) {
    //        grid[i][j] = '0';
    //
    //        for(int k = 0; k < 4; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1') {
    //                dfs(grid, x, y);
    //            }
    //        }
    //    }




    //LCR 105. 岛屿的最大面积
    // int row, col, ret, count;
    //    boolean[][] visit;
    //    int[] dx = new int[]{0, 0, 1, -1};
    //    int[] dy = new int[]{1, -1, 0, 0};
    //
    //    public int maxAreaOfIsland(int[][] grid) {
    //        row = grid.length;
    //        col = grid[0].length;
    //        visit = new  boolean[row][col];
    //
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(grid[i][j] == 1 && !visit[i][j]) {
    //                    count = 0;
    //                    dfs(grid, i, j);
    //                    ret = Math.max(ret, count);
    //                }
    //            }
    //        }
    //        return ret;
    //    }
    //
    //    private void dfs(int[][] grid, int i, int j) {
    //        count++;
    //        visit[i][j] = true;
    //
    //        for(int k = 0; k < 4; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            if(x >= 0 && x < row && y >= 0 && y < col && !visit[x][y] && grid[x][y] == 1) {
    //                dfs(grid, x, y);
    //            }
    //        }
    //    }



    //130. 被围绕的区域
    //int row, col;
    //    int[] dx = new int[]{0, 0, 1, -1};
    //    int[] dy = new int[]{1, -1, 0, 0};
    //
    //    public void solve(char[][] board) {
    //        row = board.length;
    //        col = board[0].length;
    //
    //        //  将处于边界的连通 'O'变成 '.'
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(i == 0 || i == row - 1 || j == 0 || j == col - 1) {
    //                    if(board[i][j] == 'O') dfs(board, i, j);
    //                }
    //            }
    //        }
    //
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(board[i][j] == '.') board[i][j] = 'O';
    //                else if(board[i][j] == 'O') board[i][j] = 'X';
    //            }
    //        }
    //    }
    //
    //    private void dfs(char[][] board, int i, int j) {
    //        board[i][j] = '.';
    //
    //        for(int k = 0; k < 4; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            if(x >= 0 && x < row && y >= 0 && y < col && board[x][y] == 'O') {
    //                dfs(board, x, y);
    //            }
    //        }
    //    }




    //417. 太平洋大西洋水流问题
    //    int row, col;
    //    List<List<Integer>> ret;
    //    int[] dx = new int[]{0, 0, 1, -1};
    //    int[] dy = new int[]{1, -1, 0, 0};
    //
    //    public List<List<Integer>> pacificAtlantic(int[][] heights) {
    //        row = heights.length;
    //        col = heights[0].length;
    //        boolean[][] Pacific = new boolean[row][col];
    //        boolean[][] Atlantic = new boolean[row][col];
    //        ret = new ArrayList<>();
    //
    //        // 1. 从太平洋和大西洋的所有行入口依次进行 floodFill算法，分别标记所有可以流向太平洋和大西洋的方格
    //        for(int i = 0; i < row; i++) {
    //            // 太平洋
    //            if(!Pacific[i][0]) dfs(heights, i, 0, Pacific);
    //            // 大西洋
    //            if(!Atlantic[i][col - 1]) dfs(heights, i, col - 1, Atlantic);
    //        }
    //        // 2. 从太平洋和大西洋的所有列入口依次进行 floodFill算法，分别标记所有可以流向太平洋和大西洋的方格
    //        for(int i = 0; i < col; i++) {
    //            if(!Pacific[0][i]) dfs(heights, 0, i, Pacific);
    //            if(!Atlantic[row - 1][i]) dfs(heights, row - 1, i, Atlantic);
    //        }
    //        // 3. 查找 Pacific 和 Atlantic 中都会 true的方格
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(Pacific[i][j] && Atlantic[i][j]) {
    //                    List<Integer> tmp = new ArrayList<>();
    //                    tmp.add(i); tmp.add(j);
    //                    ret.add(tmp);
    //                }
    //            }
    //        }
    //
    //        return ret;
    //    }
    //
    //    private void dfs(int[][] heights, int i, int j, boolean[][] check) {
    //        check[i][j] = true;
    //
    //        for(int k = 0; k < 4; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            if(x >= 0 && x < row && y >= 0 && y < col && !check[x][y] && heights[x][y] >= heights[i][j]) {
    //                dfs(heights, x, y, check);
    //            }
    //        }
    //    }





    //529. 扫雷游戏
    //int row, col;
    //    int[] dx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
    //    int[] dy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
    //
    //    public char[][] updateBoard(char[][] board, int[] click) {
    //        row = board.length;
    //        col = board[0].length;
    //
    //        dfs(board, click[0], click[1]);
    //        return board;
    //    }
    //    private void dfs(char[][] board, int i, int j) {
    //        if(board[i][j] == 'M') {
    //            board[i][j] = 'X';
    //            return;
    //        }
    //
    //        int count = 0;      // 记录当前位置四周雷的数量
    //        for(int k = 0; k < 8; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            if(x >= 0 && x < row && y >= 0 && y < col && board[x][y] == 'M') count++;
    //        }
    //        if(count > 0) {
    //            board[i][j] = (char) ('0' + count);
    //            return;
    //        }
    //        board[i][j] = 'B';
    //        for(int k = 0; k < 8; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            if(x >= 0 && x < row && y >= 0 && y < col && board[x][y] == 'E') dfs(board, x, y);
    //        }
    //    }





    // JZ13 机器人的运动范围
    //int ret;
    //    boolean[][] visit;
    //    int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int movingCount(int threshold, int rows, int cols) {
    //        visit = new boolean[rows][cols];
    //        dfs(0, 0, rows, cols, threshold);
    //        return ret;
    //    }
    //
    //    private void dfs(int i, int j, int rows, int cols, int threshold) {
    //        visit[i][j] = true;
    //        ret++;
    //
    //        for(int k = 0; k < 4; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            if(x >= 0 && x < rows && y >= 0 && y < cols && !visit[x][y]) {
    //                // 计算 x 和 y 的各位数之和
    //                int sum = 0, tmpx = x, tmpy = y;
    //                while(tmpx > 0 || tmpy > 0) {
    //                    sum += tmpx % 10 + tmpy % 10;
    //                    tmpx /= 10;
    //                    tmpy /= 10;
    //                }
    //                System.out.println(sum);
    //                if(sum <= threshold) dfs(x, y, rows, cols, threshold);
    //            }
    //        }
    //    }




    //62. 不同路径
    //    public int uniquePaths(int m, int n) {
    //        int[][] memo = new int[m + 1][n + 1];
    //        return dfs(m, n, memo);
    //    }
    //
    //    private int dfs(int m, int n, int[][] memo) {
    //        if(m == 0 || n == 0) return 0;
    //        if(memo[m][n] != 0) {
    //            return memo[m][n];
    //        }
    //        if(m == 1 && n == 1) {
    //            memo[m][n] = 1;
    //            return 1;
    //        }
    //        memo[m][n] = dfs(m - 1, n, memo) + dfs(m, n - 1, memo);
    //        return memo[m][n];
    //    }



    //300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        int ret = 0, n = nums.length;
        int[] memo = new int[n + 1];

        for(int i = 0; i < n; i++) {
            ret = Math.max(ret, dfs(nums, i, memo));
        }
        return ret;
    }

    // 当前位置开始的最长递增子序列
    private int dfs(int[] nums, int pos, int[] memo) {
        if(memo[pos] != 0) return memo[pos];
        int count = 1;

        for(int i = pos + 1; i < nums.length; i++) {
            if(nums[i] > nums[pos])
                count =  Math.max(count, dfs(nums, i, memo) + 1);
        }
        memo[pos] = count;
        return count;
    }



    // 375. 猜数字大小 II
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n + 1][n + 1];
        return dfs(1, n);
    }

    private int dfs(int left, int right) {
        if(left >= right) return 0;
        if(memo[left][right] != 0) {
            return memo[left][right];
        }

        int ret = Integer.MAX_VALUE;
        for(int start = left; start <= right; start++) {
            int x = dfs(left, start - 1);
            int y = dfs(start + 1, right);
            ret = Math.min(Math.max(x, y) + start, ret);
        }
        memo[left][right] = ret;
        return ret;
    }




    // LCR 112. 矩阵中的最长递增路径
    //     int ret, row, col;
    //    int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int longestIncreasingPath(int[][] matrix) {
    //        row = matrix.length;
    //        col = matrix[0].length;
    //        int[][] memo = new int[row][col];
    //
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                ret = Math.max(ret, dfs(matrix, i, j, memo));
    //            }
    //        }
    //        return ret;
    //    }
    //
    //    private int dfs(int[][] matrix, int i, int j, int[][] memo) {
    //        //visit[i][j] = true;
    //        if(memo[i][j] != 0) return memo[i][j];
    //
    //        int ret = 1;
    //        for(int k = 0; k < 4; k++) {
    //            int x = i + dx[k], y = j + dy[k];
    //            if(x >= 0 && x < row && y >= 0 && y <col && matrix[x][y] > matrix[i][j]) {
    //                ret = Math.max(ret, dfs(matrix, x, y, memo) + 1);
    //            }
    //        }
    //        memo[i][j] = ret;
    //        return ret;
    //    }


}
